package com.heima.leetcode.datastructure.binarysearchtree;

import java.util.Arrays;

/**
 * <strong>根据前序遍历结果构建二叉搜索树 1008</strong>
 * <p>题目说明：</p>
 * <p>给定的preorder数组 >= 1</p>
 * <p>给定的preorder数组没有重复元素</p>
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/12 11:35
 */
public class BuildBSTByPreOrder {

    /**
     * <h3>方法一：一个个put进去</h3>
     * 根据前序遍历结果构建二叉搜索树
     *
     * @param preorder 前序遍历结果
     * @return 构建好的树的根节点
     */
    public static TreeNode bstFromPreorder1(int[] preorder) {
        TreeNode root = new TreeNode(preorder[0]);
        for (int i = 1; i < preorder.length; i++) {
            // put1(root, preorder[i]);
            put2(root, preorder[i]);
        }
        return root;
    }

    /**
     * <h3>方法二：找到左子树和右子树的范围，递归构建</h3>
     * 根据前序遍历结果构建二叉搜索树
     *
     * @param preorder 前序遍历结果
     * @return 构建好的树的根节点
     */
    public static TreeNode bstFromPreorder2(int[] preorder) {
        return bstFromPreorder(preorder, 0, preorder.length - 1);
    }

    /**
     * 非递归实现put
     *
     * @param root   树的根节点
     * @param target 待插入
     */
    @SuppressWarnings("all")
    private static void put1(TreeNode root, int target) {
        TreeNode curr = root;
        TreeNode parent = null;
        while (curr != null) {
            if (target < curr.val) {
                parent = curr;
                curr = curr.left;
            } else if (curr.val < target) {
                parent = curr;
                curr = curr.right;
            }
        }
        if (target < parent.val) {
            parent.left = new TreeNode(target);
        } else {
            parent.right = new TreeNode(target);
        }
    }

    /**
     * 用递归方式实现
     *
     * @param root   当前树的根节点
     * @param target 待插入
     * @return 当前树插入节点后的根节点
     */
    private static TreeNode put2(TreeNode root, int target) {
        if (root == null) {
            return new TreeNode(target);
        }
        if (target < root.val) {
            root.left = put2(root.left, target);
        } else {
            root.right = put2(root.right, target);
        }
        return root;
    }

    /**
     * 递归实现方法二
     * @param preorder 全部树的前序遍历结果
     * @param start 当前树的前序遍历结果的开始索引（包含）
     * @param end 当前树的前序遍历结果的结束索引（包含）
     * @return 构建好当前树的根节点
     */
    private static TreeNode bstFromPreorder(int[] preorder, int start, int end) {
        if (start > end) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[start]);
        for (int i = start; i <= end; i++) {
            if (preorder[i] > root.val) { // 找得到右子树
                root.left = bstFromPreorder(preorder, start + 1, i - 1);
                root.right = bstFromPreorder(preorder, i, end);
                return root;
            }
        }
        root.left = bstFromPreorder(preorder, start + 1, end);
        return root;
    }
}
